Classical algorithms for market equilibrium computation such as proportional response dynamics face scalability issues with Internet-based applications such as auctions, recommender systems, and fair division, despite having an almost linear runtime in terms of the product of buyers and goods. In this work, we provide the first quantum algorithm for market equilibrium computation with sub-linear performance. Our algorithm provides a polynomial runtime speedup in terms of the product of the number of buyers and goods while reaching the same optimization objective value as the classical algorithm. Numerical simulations of a system with 16384 buyers and goods support our theoretical results that our quantum algorithm provides a significant speedup.

Weaknesses: After reading the authors response, I am convinced by the contribution of the authors. I really hope that they will include the answers that they provided to the final version of the paper because I find that it totally changes the reader's understanding of the paper. In particular, regarding the fact that obtaining a linear convergence rate is not obvious and was not done before. First, I found the novelty of the work a bit limited because not enough novelty was given in the "theory" side nor in the "numerical" side. The paper seems to "just" apply convex optimization methods to finding market equilibria and giving theoretical justifications for why this approach is sound.

There was initially some concern that this paper didn't have highly significant results since it appears to be the case that your work is reducing the problem of equilibrium computation to convex optimization. However, after some consideration, the reviewers were swayed by your rebuttal and agreed that the results were not trivial, the topic was interesting, and this appears to be an interesting application of optimization methods. We decided to accept your paper for NeurIPS this year, but we would strongly suggest that you incorporate some of the comments in your rebuttal into the main document, to better highlight the novelty. We strongly encourage you to take into account Reviewer 4's comments, who carefully went through the paper.

Market equilibrium is a solution concept with many applications such as digital ad markets, fair division, and resource sharing. For many classes of utility functions, equilibria can be captured by convex programs. We develop simple first-order methods suitable for solving these programs for large-scale markets. We focus on three practically-relevant utility classes: linear, quasilinear, and Leontief utilities. Using structural properties of market equilibria under each utility class, we show that the corresponding convex programs can be reformulated as optimization of a structured smooth convex function over a polyhedral set, for which projected gradient achieves linear convergence.